/*
 * @lc app=leetcode.cn id=139 lang=cpp
 *
 * [139] 单词拆分
 */

// @lc code=start
class Solution
{
public:
  bool wordBreak(string s, vector<string>& wordDict)
  {
    int n = s.size();
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (dp[j] && words.find(s.substr(j, i - j)) != words.end()) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[n];
  }
};
// @lc code=end
